To improve throughput, many communication systems implement a forward error correction (FEC) technique. This is particularly true of wireless communication systems, such as cellular networks. One of the most common FEC techniques is known as convolutional coding with Viterbi decoding. This technique is particularly useful for channels in which additive white Gaussian noise distorts the transmitted signal. A Viterbi decoder is the maximum likelihood sequence decoder for a convolutional code. The Viterbi algorithm is based on the dependency between consecutive transmitted bits. In order to detect the original information bits, the decoder builds a record of limited possible history transmitted bits based on the dependency of the bits. This history chain is called a trellis and usually requires a dedicated memory block to save all possible history paths.
The size of the trellis memory in bits (TMS) depends on the depth of the dependency between the transmitted bits (called constraint length, or K) and the block size of the information bits (N). Generally, TMS=(2K-1)×N. Therefore, the size of the trellis memory increases linearly with N and exponentially with K. For example, in WCDMA, K=9, which means that for a block size of 1024 bits, the required trellis memory is 256*1024=256 Kbits or 32 Kbyte of memory. This size of memory can significantly increase the total size of the decoder hardware.
In order to overcome the problems caused by a large memory size, several solutions have been introduced, including a sliding window approach that cuts down the original block into sub-blocks and processes each sub-block separately. This approach performs both a feed-forward and a traceback process on each sub-block. The feed-forward process is performed while the path metric state from a previous sub-block is restored, and a learning period is performed during the traceback process. However, in order to process each sub-block separately while restoring path metrics and performing learning periods, this approach requires a large overhead MIPS time from a host processor. Therefore, there is a need in the art for a Viterbi decoder capable of decoding data using a reduced trellis memory while minimizing performance degradation.